Best meeting point

Time: O(MxN); Space: O(M+N); hard

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example 1:

Input: grid =

[
    [1, 0, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0]
]

Output: 6

Explanation:

  • Given three people living at (0,0), (0,4), and (2,2).

  • The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal.

Thought Process

  1. Brute Force

    • Try every point and calculate the 1’s distance to this point

    • The best distance can be found by using min function

    • Time complexity O(m2n2) Space complexity O(mn)

  2. Sorting

    • The optimal point is at the mean. For example, 1-1-0-0-1, the optimal point is at x = 1, and assume the total distance is d

    • If we move the point to the right, x = 2, the total distance will be d + 2 - 1, since there will be two points on its left and 1 point on its right

    • For even number of 1’s, we can pick either one of middle as the choice, for example 1-1-0-0-1-1 Time complexity: O(MxN + MxNxLog(MxN)) = O(MxNxLog(MxN)) Space complexity: O(MxN)

  3. Without Sorting

    • Write separate function for collecting rows and col Time complexity: O(MxN) Space complexity: O(MxN)

  4. Two Pointers

    • We can modify the distance function to use two pointers, using highIndex - lowIndex Time complexity: O(MxN) Space complexity: O(MxN)

  5. One pass with Count

    • We can modify the distance function to use frequency to find the reach the median Time complexity: O(MxN) Space complexity: O(MxN)

[7]:

from random import randint

class Solution1(object):
    def minTotalDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        x = [i for i, row in enumerate(grid) for v in row if v == 1]
        y = [j for row in grid for j, v in enumerate(row) if v == 1]
        mid_x = self.findKthLargest(x, len(x) // 2 + 1)
        mid_y = self.findKthLargest(y, len(y) // 2 + 1)

        return sum([abs(mid_x-i) + abs(mid_y-j) \
                   for i, row in enumerate(grid) for j, v in enumerate(row) if v == 1])

    def findKthLargest(self, nums, k):
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot_idx = randint(left, right)
            new_pivot_idx = self.PartitionAroundPivot(left, right, pivot_idx, nums)
            if new_pivot_idx == k - 1:
                return nums[new_pivot_idx]
            elif new_pivot_idx > k - 1:
                right = new_pivot_idx - 1
            else:  # new_pivot_idx < k - 1.
                left = new_pivot_idx + 1

    def PartitionAroundPivot(self, left, right, pivot_idx, nums):
        pivot_value = nums[pivot_idx]
        new_pivot_idx = left
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        for i in range(left, right):
            if nums[i] > pivot_value:
                nums[i], nums[new_pivot_idx] =  nums[new_pivot_idx], nums[i]
                new_pivot_idx += 1

        nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right]
        return new_pivot_idx

[9]:

s = Solution1()
grid = [[1, 0, 0, 0, 1],
        [0, 0, 0, 0, 0],
        [0, 0, 1, 0, 0]
]
assert s.minTotalDistance(grid) == 6